#include <stdio.h>
#include <stdlib.h>
#include "sqstring.cpp"

void getnext(sqstring t, int next[]) {
    int j = 0, k = -1;
    next[0] = -1;
    while (j < t.length - 1) {
        if (k == -1 || t.data[j] == t.data[k]) {
            j++;
            k++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}

void display(sqstring s, sqstring t, int i, int j) {
    int k;
    printf(" ");
    for (k = 0; k < i; k++)
        printf(" ");
    printf(" i=%d,j=%d\n", i, j);
    printf("s:");
    for (k = 0; k < s.length; k++)
        printf("%c", s.data[k]);
    printf("\n");
    printf("t:");
    for (k = 0; k < i - j; k++)
        printf(" ");
    for (k = 0; k < s.length; k++)
        printf("%c", t.data[k]);
    printf("\n");
    for (k = 0; k < i - j; k++)
        printf(" ");
    for (k = 0; k <= j; k++)
        printf(" ");
    printf(" \n");
}

int count(sqstring s, sqstring t) {
    int next[maxsize], i = 0, j = 0, count = 0;
    getnext(t, next);
    display(s, t, i, j);
    while (i < s.length && j < t.length) {
        if (j == -1 || s.data[i] == t.data[j]) {
            i++;
            j++;
        } else {
            j = next[j];
            display(s, t, i, j);
        }
        if (j == t.length) {
            display(s, t, i, j);
            printf("\t匹配成功1次\n");
            count++;
            j = 0;
        }
    }
    return count;
}

int main() {
    sqstring s, t;
    strassign(s, "aaaaa");
    strassign(t, "aa");
    printf("t在s中出现的次数：%d\n", count(s, t));
    destroystr(s);
    destroystr(t);
    return 0;
}